package randomthoughts.dp;

/**
 * @author tongchen
 * @create 2023-04-18 10:56
 */
public class PacketMoneyChange {
    public static void main(String[] args) {

    }

    /**LeetCode 322
     *1.dp[i]:组成和为i最少需要多少个零钱，i是要组成的和；2.递推公式：dp[i]=min(dp[i],dp[i-coins[i]]+1)3.初始化：组成0元的零钱方式有0种
     * ，所以dp[0]=0，因为是比较最小值其他值初始化为max，所以;4.遍历顺序：由前面的公式推出后面的，所以是从前往后遍历
     *
     * @return
     */
    public static int changeMoney(int[]coins,int target){
        //创建dp数组，
        int[]dp=new int[target+1];
        //初始化
        for(int i=1;i<dp.length;++i){
            dp[i]=Integer.MAX_VALUE;
        }
        //进行遍历(先物品后容量)
        for(int i=0;i<coins.length;++i ){
            for (int j = coins[i]; j <=target ; j++) {
                if(dp[j-coins[i]]!=Integer.MAX_VALUE)
                    //防止溢出，如果dp[j-coins[i]]是最大值，那么其实也没有选择的必要
                dp[i]=Math.min(dp[j],dp[j-coins[i]]+1);
            }
        }
        return dp[target];
    }
}
